package com.lllkey.dp01bag;

public class MyDp01Bag {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		for (int i = 0; i < 50; i++) {
			doTest(i + 1);
		}
//		for (int i = 0; i < 50; i++) {
//			doTest(i + 1);
//		}
	}

	/**
	 * 测试算法
	 * 
	 * @param count
	 *            当前运行第几个
	 */
	private static void doTest(int count) {
		int W_NUM = 3;
		int m = 10;
		m = (int) (Math.random() * (100) + 100);
		// m = 150;
		W_NUM = (int) (Math.random() * (40 - 15) + 15);
		int wight[] = new int[W_NUM];
		int value[] = new int[W_NUM];
		int c[][] = new int[W_NUM + 1][m + 1];
		// init
		for (int i = 0; i < W_NUM; i++) {
			wight[i] = i + 3;
			value[i] = i + 4;
			wight[i] = (int) (Math.random() * (10) + 2);
			value[i] = (int) (Math.random() * (10) + 4);
		}
		for (int i = 0; i < W_NUM + 1; i++) {
			for (int j = 0; j < m + 1; j++) {
				c[i][j] = 0;
			}
		}
		long time = System.nanoTime();
		knapsack(W_NUM, m, wight, value, c);
		System.out.print(count + " \t物品数量: " + W_NUM + " \t总质量M: " + m
				+ " \t最优结果: " + c[W_NUM][m] + " \tn*c: "
				+ (W_NUM * c[W_NUM][m]));
		System.out.println(" \t执行时间: " + (System.nanoTime() - time) + "ns");
	}

	/**
	 * 动态规划算法
	 * 
	 * @param W_NUM
	 *            共有物品个数
	 * @param m
	 *            总质量
	 * @param wight
	 *            每个物品的重量数组
	 * @param value
	 *            每个物品价值数组
	 * @param c
	 *            缓存数组
	 */
	private static void knapsack(int W_NUM, int m, int[] wight, int[] value,
			int[][] c) {
		for (int i = 1; i < W_NUM + 1; i++) {
			for (int j = 1; j < m + 1; j++) {
				if (j >= wight[i - 1]) {
					c[i][j] = Math.max(c[i - 1][j - wight[i - 1]]
							+ value[i - 1], c[i][j - 1]);
				} else {
					c[i][j] = c[i - 1][j];
				}
			}
		}
		// // test
		// for (int i = 0; i < W_NUM + 1; i++) {
		// for (int j = 0; j < m + 1; j++) {
		// System.out.print(c[i][j] + " ");
		// }
		// System.out.println();
		// }
	}
}
